Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths

摘要

Let $G$ be an $n$-node simple directed planar graph with nonnegative edgeweights. We study the fundamental problems of computing (1) a global cut of $G$with minimum weight and (2) a~cycle of $G$ with minimum weight. The bestpreviously known algorithm for the former problem, running in $O(n\log^3 n)$time, can be obtained from the algorithm of \Lacki, Nussbaum, Sankowski, andWulff-Nilsen for single-source all-sinks maximum flows. The best previouslyknown result for the latter problem is the $O(n\log^3 n)$-time algorithm ofWulff-Nilsen. By exploiting duality between the two problems in planar graphs,we solve both problems in $O(n\log n\log\log n)$ time via a divide-and-conqueralgorithm that finds a shortest non-degenerate cycle. The kernel of our resultis an $O(n\log\log n)$-time algorithm for computing noncrossing shortest pathsamong nodes well ordered on a common face of a directed plane graph, which isextended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsenfor an undirected plane graph.